package com.zfl;

public class FindTargetSumWays {

    public int findTargetSumWays(int[] nums, int target) {

        int n = nums.length;

        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }

        if (Math.abs(target)>sum) {
            return 0;
        }

        if ((target+sum)%2!=0) {
            return 0;
        }


        int subSum = (target+sum)/2;

        if (subSum<0) {
            return 0;
        }

        return this.findTargetSum(nums,subSum);
    }

    private int findTargetSum(int[] nums,int target) {
        int n = nums.length;
        int[][] dp =  new int[n+1][target+1];

        for (int i = 0; i < dp.length; i++) {
            dp[i][0] =  1;
        }

        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < target+1; j++) {
                int currentNum = nums[i-1];
                dp[i][j] = dp[i-1][j];
                if (currentNum<=j) {
                    dp[i][j]+=dp[i-1][j-currentNum];
                }
            }
        }
        return dp[n][target];
    }
}
